The approaches described in this section could be pursued but are not necessarily approaches that have previously been conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.
Computer file systems are usually constructed as objects and references pointing to these objects. The objects are located in an object store. An object may have many references pointing to it; additionally, the object itself can hold references that point to other objects. Thus, typically data is organized as graphs of data objects, and, more specifically, as directed acyclic graphs. In order to effectively utilize resources of various storage devices, it is important to set up a procedure for removing objects that are no longer needed.
Building a file system for an immutable data store may involve eventually deleting and reclaiming storage space associated with obsolete data. Never reclaiming space and just adding new storage as needed is an approach that can also be utilized. This approach has a number of advantages, not least of which is its simplicity. However, this approach is not practical for a commercial product.
Furthermore, extensive use of snapshots (versions of file systems) and deduplication of data involves determining whether a given object is still in use and requires analysis of the full object graph.
A special technique, referred to as garbage collection (GC), can be applied to analyze the object graph to find and remove objects that are no longer referenced by other objects. Some traditional GC techniques use mark and collection techniques to remove the unreferenced objects from the object store and to reclaim the space in a memory, hard disk, or other storage device where the data object store is located.